//
// Created by hay boy on 2022/7/22.
//

#ifndef ALGORITHMS_MAXHBLT_H
#define ALGORITHMS_MAXHBLT_H
#include <sstream>
#include "maxPriorityQueue.h"
#include "../queue/QueueException.h"
#include "../tree/binaryTree/linkedBinaryTree.h"
using namespace std;

template<class T>
class maxHblt : public maxPriorityQueue<T>, public linkedBinaryTree<pair<int,T>>{
private:
    void meld(binaryTreeNode<pair<int,T>>*&,binaryTreeNode<pair<int,T>>*&);
    static void hbltOutput(binaryTreeNode<pair<int,T>> *t){
        cout<<t->element.second<<' ';
    }
public:
    bool empty()const{
        return linkedBinaryTree<pair<int,T>>::treeSize==0;
    }
    int size() const{
        return linkedBinaryTree<pair<int,T>>::treeSize;
    }
    const T& top(){
        if(linkedBinaryTree<pair<int,T>>::treeSize==0){
            throw QueueEmpty();
        }
        return linkedBinaryTree<pair<int,T>>::root->element;
    }
    void pop();
    void push(const T&);
    void initialize(T*,int);
    void meld(maxHblt<T>& theHblt){
        meld(linkedBinaryTree<pair<int,T>>::root,theHblt.root);
        linkedBinaryTree<pair<int,T>>::treeSize += theHblt.treeSize;
        theHblt.root = nullptr;
        theHblt.treeSize = 0;
    }
    void output(){
        linkedBinaryTree<pair<int,T>>::postOrder(hbltOutput());
        cout<<endl;
    }

};

template<class T>
void maxHblt<T>::meld(binaryTreeNode<pair<int, T>> *&x, binaryTreeNode<pair<int, T>> *&y) {
    if(y == nullptr){
        return;
    }
    if(x == nullptr){
        x = y;
        return;
    }
    if(x->element.second<y->element.second){
        swap(x,y);
    }
    meld(x->rightChild,y);
    if(x->leftChild == nullptr){
        x->leftChild = x->rightChild;
        x->rightChild = nullptr;
        x->element.first = 1;
    }else{
        if(x->leftChild->element.first<x->rightChild.element.first){
            swap(x->leftChild,x->rightChild);
        }
        x->element.first = x->rightChild->element+1;
    }

}

template<class T>
void maxHblt<T>::push(const T &theElement) {
    binaryTreeNode<pair<int,T>> *q = new binaryTreeNode<pair<int,T>>(pair<int,T>(1,theElement));
    meld(linkedBinaryTree<pair<int,T>>::root,q);
    linkedBinaryTree<pair<int,T>>::treeSize++;
}

template<class T>
void maxHblt<T>::pop() {
    if(linkedBinaryTree<pair<int,T>>::root == nullptr){
        throw QueueEmpty();
    }
    binaryTreeNode<pair<int,T>> *left = linkedBinaryTree<pair<int,T>>::root->leftChild,
                                *right = linkedBinaryTree<pair<int,T>>::root->rightChild;
    delete linkedBinaryTree<pair<int,T>>::root;
    linkedBinaryTree<pair<int,T>>::root = left;
    meld(linkedBinaryTree<pair<int,T>>::root,right);
    linkedBinaryTree<pair<int,T>>::treeSize--;
}

template<class T>
void maxHblt<T>::initialize(T * theElement, int theSize) {
    ArrayQueue<binaryTreeNode<pair<int,T>>*> q(theSize);
    linkedBinaryTree<pair<int,T>>::erase();
    for(int i = 1;i <= theSize;i++){
        q.push(new binaryTreeNode<pair<int,T>>(pair<int,T>(1,theElement)));
    }
    for(int i = 1;i <= theSize-1;i++){
        binaryTreeNode<pair<int,T>> *b  = q.front();
        q.pop();
        binaryTreeNode<pair<int,T>> *c = q.front();
        q.pop();
        meld(b,c);
        q.push(b);
    }
    if(theSize>0){
        linkedBinaryTree<pair<int,T>>::root = q.front();
    }
    linkedBinaryTree<pair<int,T>>::treeSize = theSize;
}

#endif //ALGORITHMS_MAXHBLT_H
